package code;


public class Median {
	
	/*
	 * �������ת��Ϊһ������ձ��Ե����⣬��֪�������������,��ϲ���ĵ�k����
	 * ˼·��
	 * �Ƚ�A[k/2]��B[k/2]�Ĺ�ϵ
	 * A,B�ĳ��ȶ�����k/2
	 * if A[k/2]<B[k/2],then A[0...k/2]����cause A[0...k/2]�������ǵ�k�����
	 * if A[k/2]>B[k/2],then B[0...k/2]����
	 * if A[k/2]=B[k/2] then A[k/2]Ϊ��
	 */
	
	public double findKth(int a[],int n,int[] b,int m,int k){
		/*
		 * a����ĳ���С��b����
		 */
		if(n>m){
			return findKth(b,m,a,n,k);
		}
		if(n==0){
			return b[k-1];
		}
		if(k==1){
			return a[0]>b[0]?b[0]:a[0];
		}
		
		int pa=k/2>n?n:k/2;
		int pb=k-pa;
		if(a[pa-1]<b[pb-1]){
			int[] ta=new int[n-pa];
			for(int i=pa;i<n;i++)
				ta[i-pa]=a[i];
			return findKth(ta,n-pa,b,m,k-pa);
		}
		else if(a[pa-1]>b[pb-1]){
			int[] tb=new int[m-pb];
			for(int i=pb;i<m;i++)
				tb[i-pb]=b[i];
			return findKth(a,n,tb,m-pb,k-pb);
		}
		else return a[pa-1];
	}
	
    public double findMedianSortedArrays(int A[], int B[]) {
    	
    	int n=A.length;
    	int m=B.length;
    	int total=n+m;
    	if(total%2==1){
    		return findKth(A,n,B,m,total/2+1);
    	}
    	else{
    		return (findKth(A,n,B,m,total/2)
    				+findKth(A,n,B,m,total/2+1))/2;
    	}
    }
    public static void main(String[] args){
    	int[] A={2,4,5,6,7,8,9};
    	int[] B={1,4};
    	Median median=new Median();
    	System.out.println(median.findMedianSortedArrays(B, A));
    }
}
